package com.fang.algorithm.sort.selection;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * @date 2022/1/5 3:18 下午
 **/
public class Test02_Example {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 5, 6, 4};
        int kthLargest = findKthLargest(arr, 2);
        System.out.println(kthLargest);
    }

    public static int findKthLargest(int[] nums, int k) {
        int maxIndex;
        // 执行 k 次选择
        for (int i = 0; i < k; i++) {
            maxIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[maxIndex] < nums[j]) {
                    // 记录最大值的下标
                    maxIndex = j;
                }
            }
            // 将最大元素交换至首位
            arrSwap(nums, i, maxIndex);
        }
        return nums[k - 1];
    }

    private static void arrSwap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
